package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/7/26.<br><br>
 *
 * 寻找重复数
 */
public class Topic287 {

    public static void main(String[] args) {
        Topic287 instance = new Topic287();

        int[] array = new int[] {1,3,4,2,2};
        System.out.println(instance.findDuplicate(array));

        array = new int[] {3,1,3,4,2};
        System.out.println(instance.findDuplicate(array));

        array = new int[] {1,1};
        System.out.println(instance.findDuplicate(array));

        array = new int[] {1,1,2};
        System.out.println(instance.findDuplicate(array));

        array = new int[] {1,3,4,2,1};
        System.out.println(instance.findDuplicate(array));
    }

    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        while (slow != fast);

        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }

    public int findDuplicate3(int[] nums) {
        int[] temp = new int[nums.length];

        int i = 0;
        while (temp[nums[i]] == 0) {
            temp[nums[i]] = nums[i];
            i++;
        }

        return nums[i];
    }

    public int findDuplicate2(int[] nums) {
        int low = 1;
        int high = nums.length - 1;
        int mild = (low + high) / 2;

        while (low <= high) {
            int counter = 0;
            for(int value : nums) {
                if(value < mild) {
                    counter++;
                }
            }

            if(counter < mild) {
                low = mild + 1;
            }
            else {
                high = mild - 1;
            }

            mild = (low + high) / 2;
        }

        return mild;
    }
}
